import static org.junit.Assert.assertArrayEquals;
/**
 *  * 这是 LeetCode 第 189. 轮转数组 的解决方案
 *  https://leetcode.cn/problems/rotate-array
 */
class RotateArray{

    /**
     * 方法一：新数组
     * 功能：将数组 nums 向右旋转 k 位。
     * 实现逻辑：创建一个新数组，将原数组的每个元素放到新数组的对应位置。
     * 时间复杂度：O(n)，其中 n 是数组的长度。
     * 空间复杂度：O(n)，使用了一个额外的数组来存储结果。
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        if(len == 0 || k == 0){
            return;
        }
        int[] newArr = new int[len];
        for(int i = 0; i < len; i++){
            newArr[(i + k) % len] = nums[i];
        }
        for(int i = 0; i < len; i++){
            nums[i] = newArr[i];
        }
    }
    /**
     * 方法二：环状替换
     * 功能：将数组 nums 向右旋转 k 位。
     * 实现逻辑：通过环状替换的方式，将每个元素放到其旋转后的位置。
     * 时间复杂度：O(n)，其中 n 是数组的长度。
     * 空间复杂度：O(1)，只使用了常数级别的额外空间。
     * @param nums
     * @param k
     */
    public void rotate2(int[] nums, int k) {
        int len = nums.length;
        if(len == 0 || k == 0){
            return;
        }
        k %= len;
        int count = gcd(k, len);
        for(int start = 0; start < count; start++){
            int current = start;
            int pre = nums[start];
            while(true){
                int next = (current + k) % len;
                int temp = nums[next];
                nums[next] = pre;
                pre = temp;
                current = next;
                if(start == current){
                    break;
                }
            }
        }
    }

    private int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a % b);
    }

    /**
     * 方法三：数组翻转
     * 功能：将数组 nums 向右旋转 k 位。
     * 实现逻辑：
     * 1. 计算有效旋转步数：k %= len; 确保 k 不超过数组长度。
     * 2. 反转整个数组：reverse(nums, 0, len - 1);
     * 3. 反转前 k 个元素：reverse(nums, 0, k - 1);
     * 4. 反转剩余的元素：reverse(nums, k, len - 1);
     * reverse 方法用于反转数组中从索引 i 到索引 j 的元素。
     * 时间复杂度：O(n)，其中 n 是数组的长度。
     * 空间复杂度：O(1)，只使用了常数级别的额外空间。
     * @param nums
     * @param k
     */
    public void rotate3(int[] nums, int k) {
        int len = nums.length;
        if(len == 0 || k == 0){
            return;
        }
        k %= len;
        reverse(nums, 0, len -1);
        reverse(nums, 0, k -1);
        reverse(nums, k, len - 1);
    }

    private void reverse(int[] nums, int i, int j){
        while(i < j){
            int temp = nums[i];
            nums[i++] = nums[j];
            nums[j--] = temp;
        }
    }

    public static void main(String[] args) {
        RotateArray solution = new RotateArray();
        try {
            solution.testRotate2();
            System.out.println("\nAll test cases passed successfully!");
        } catch (AssertionError e) {
            System.out.println("\nTest failed: " + e.getMessage());
        }
    }

    private void testRotate2() {
        RotateArray solution = new RotateArray();

        // 测试用例1：常规数组，包含重复元素
        int[] nums1 = {1, 2, 3, 4, 5, 6};
        solution.rotate2(nums1, 2);
        assertArrayEquals(new int[]{5, 6, 1, 2, 3, 4}, nums1);
        System.out.println("Test Case 1 Passed");

        // 测试用例2：数组长度为1
        int[] nums2 = {1};
        solution.rotate2(nums2, 1);
        assertArrayEquals(new int[]{1}, nums2);
        System.out.println("Test Case 2 Passed");

        // 测试用例3：k为0
        int[] nums3 = {1, 2, 3, 4, 5, 6};
        solution.rotate2(nums3, 0);
        assertArrayEquals(new int[]{1, 2, 3, 4, 5, 6}, nums3);
        System.out.println("Test Case 3 Passed");

        // 测试用例4：k大于数组长度
        int[] nums4 = {1, 2, 3, 4, 5, 6};
        solution.rotate2(nums4, 8);
        assertArrayEquals(new int[]{5, 6, 1, 2, 3, 4}, nums4);
        System.out.println("Test Case 4 Passed");

        // 测试用例5：数组为空
        int[] nums5 = {};
        solution.rotate2(nums5, 3);
        assertArrayEquals(new int[]{}, nums5);
        System.out.println("Test Case 5 Passed");
    }
}